package dynamic;

/**
 * 题目：爬楼梯的最小代价
 *
 * @Author Gavin
 * @date 2022.01.09 17:54
 */
public class solution_8 {
    /**
     * 解题思路：
     * C: 1  2  4  2
     * 每一次只能走一步或者两步
     * 首先状态方程为：
     * d(i)=min(d(i-1),d(i-2))+c(i)
     * d(0)=c(0)
     * d(1)=c(1)
     * <p>
     * 主要思路就是判断走一步和走两步对应下标值的和的大小，取最小的就是最小代价
     */
    //Time:O(n) Space:O(n)
    public int solution(int[] cost) {
        if (cost == null || cost.length == 0) return 0;
        if (cost.length == 1) return cost[0];
        int n = cost.length;
        int[] d = new int[n];
        d[0] = cost[0];
        d[1] = cost[1];
        for (int i = 2; i < n; i++) {
            d[i] = Math.min(d[i - 1], d[i - 2]) + cost[i];
        }
        return Math.min(d[n - 1], d[n - 2]);
    }

    //Time:O(n) Space:O(1)
    public int solution_2(int[] cost) {
        if (cost == null || cost.length == 0) return 0;
        if (cost.length == 1) return cost[0];
        int n = cost.length;
        int first = cost[0], second = cost[1];
        for (int i = 2; i < n; i++) {
            int cur = Math.min(first, second)+ cost[i];
            first = second;
            second = cur;
        }
        return Math.min(first, second);
    }
}
